1. Field of the Disclosure
The present disclosure relates to search engines for solving combinatorial optimization problems, and more particularly, relates to computer-implemented methods and software architectures for implementing constraint propagation and retraction algorithms.
2. Description of the Related Art
Constraint Programming (CP) methods are applicable to solving hard combinatorial optimization problems such as scheduling, planning, configuration, routing, resource allocation, timetabling, and rostering. Constraint propagation, which is a central technology employed in many CP systems, uses the constraints defined in a given problem model to greatly reduce the size of the search space that is searched to find solutions to a combinatorial optimization problem. Since the size of the search space for combinatorial problems is generally exponential in the size of the problem (e.g., the number of variables in the problem model), reducing the size of this search space using constraint propagation algorithms is frequently essential for solving large problems where a significant fraction of the points in the search space may need to be visited in order to find a solution.
An effective approach for speeding up search is to reduce the search space as much as possible after every step of the search. Constraint propagation enforces a certain level of constraint consistency that results in a smaller search space. Typically in constraint programming, constraint propagation is intermixed with a search method that is used to derive new constraints. These new constraints are then propagated by the constraint propagation algorithm. The intended result is to reduce the search space as the search method explores those regions of the search space which remain after constraint propagation.
Many constraint propagation methods use variants and enhancements of the arc consistency (A/C) algorithm (see, e.g., [Mackworth77]). It is known that use of the A/C algorithm mathematically guarantees that every value in the domain of a variable is allowed by the constraints on this variable, given the current domains of the other variables in the problem model. Values removed by the A/C algorithm are not part of any feasible assignment of the variables under the constraints of the problem model. However, not every value remaining in the domain after use of A/C is necessarily part of a feasible complete solution. Accordingly, a search must still be performed to find actual feasible solutions from within the reduced search space.
Arc-consistency defined for constraints that involve more than two variables is called generalized arc-consistency. A Constraint Satisfaction Problem (CSP) is generalized-arc-consistent (or “hyper arc-consistent”) if:
for every variable x in V,
and every constraint c(x, y1, . . . , yn) involving x,
for every value d in the domain of x, D(x)
there are values d1, . . . , dn in D(y1), . . . , D(yn)
such that c(d, d1, . . . , dn) is true (equivalently, the tuple (d, d1, . . . , dn) is in c).
In the CP literature, the A/C enforcing mechanism variously consists of activating a constraint and computing an arc-consistent state after one or several value removals and hence the global propagation loop is directed by constraints (constraint-centered). Alternatively, the global propagation loop is driven by domain reductions (variable-centered).
Traditional monotonic constraint propagation (such as arc-consistency and its variants) is an important part of a CP system, and well-understood and efficient algorithms are known (see, e.g., [Bessiére01]). Monotonic constraint methods typically remove values from the domains of variables that do not satisfy the constraints on these variables.
Non-monotonic constraint propagation methods, like monotonic constraint propagation methods, can remove values that do not satisfy the constraints. However, unlike monotonic methods, non-monotonic methods are also able to put back values into variable domains if the constraints on those variables are retracted. Non-monotonic constraint propagation is less well developed, and the complexity of non-monotonic algorithms generally is greater than monotonic constraint propagation algorithms. Combinatorial optimization applications in which a problem changes dynamically, as well as Mixed-Initiative (MI) applications in which the user interacts with the system, can be equivalent to the addition and/or retraction of constraints in the problem model. The run-time performance and search memory needed for constraint propagation and/or retraction can vary greatly for different implementations of non-monotonic methods.
Constraint retraction is a widely used technique in non-monotonic constraint propagation methods. Constraint retraction may occur in a search during backtracking and user interaction and in dynamic problems. If a constraint is retracted, domain reduction that has occurred directly or indirectly due to the presence of the retracted constraint is undone by the system. Different dynamic constraint retraction algorithms have different implementation difficulty, memory requirements, and running efficiency (see, e.g., [Neveu94] and [Bartak04]). Each algorithm has particular advantages and disadvantages and can be selected for use by the constraint propagation engine to suit specific requirements of a combinatorial optimization application.
The CHOCO algorithm, for example, utilizes an event-based constraint propagation algorithm (see, e.g., [Laburthe00]). During propagation, each time a variable domain is reduced (called a variable event), the constraints involving that variable are processed, and in turn, these constraints generate new variable events thus removing more values from the domains of their argument variables. The CHOCO algorithm considers the following propagation events for finite domain variables:
INCINF: the domain lower bound is increased
DECSUP: the domain upper bound is decreased
INSTANTIATE: the domain is reduced to a single value
REMOVAL: some value a is removed from the domain
All variable events in the CHOCO algorithm have the same life-cycle: they are first generated, then the domain modification is applied, then they are stored in an event queue, and finally they are removed from the queue and executed by awakening the corresponding constraints (except the one that caused the event). At run-time, this life-cycle can stop at the domain modification step if the event does not add new information to the current status of the domain (i.e. does not change it). When a constraint is awakened, it can either be immediately propagated or delayed until all variable events have been processed. Thus propagation can be either variable-directed or constraint-directed.
There are different strategies for performing constraint propagation. For example, in a Depth-First Search, when a variable event is executed, all children variable events resulting from the constraint propagation are propagated before other pending variable events. In contrast, in a Breadth-First Search, variable events are propagated by generation. The choice of the CP strategy will depend on the combinatorial optimization application. For example, in the CHOCO algorithm, all INSTANTIATE events are stored in a Last-In-First-Out (LIFO) queue, all REMOVAL events are stored in a separate First-In-First-Out (FIFO) queue, and all INCINF and SUPINF events are stored in another FIFO queue. The order of propagation then is defined as follows: 0) all INSTANTIATE events; 1) all REMOVAL events; 2) all INCINF and DECSUP events; 3) all touched constraints defined explicitly as feasible tuples; 4) all delayed constraints with linear runtime; 5) all delayed constraints with sub-quadratic runtime; 6) all delayed constraints with quadratic runtime; and 7) all delayed constraints with higher complexity runtime. Since global constraints are often awakened after several variable events have occurred, such constraints need to take a global view of what has changed; hence global constraints consider the changes as an abstract event (e.g., “something has changed”). Some global constraints have special abstract events which contain more detailed information.
Previous constraint programming systems have selected a particular constraint propagation architecture and have hardwired it into a search engine (also known as a reasoning engine). Some systems use constraint-centered methods and others use variable-centered methods. Naive implementations of the CP architecture may be very inefficient. Recent work on the CHOCO constraint programming system takes some advantage of propagating constraints in an intelligent order depending on their domain reduction power (see, e.g., [Laburthe00]). Researchers have studied the effectiveness of implementing different constraint propagation strategies (see, e.g., [Schulte04]); however, these strategies also have been hard-coded into the search engine.
When new propagation strategies are added, the internal code of the search engine at the very lowest levels must be reprogrammed. For example, this was the experience of researchers who implemented the PALM system on top of the CHOCO kernel (see, e.g., [Jussein00b]). The PALM extension to CHOCO incorporated non-monotonic propagation To integrate new functionality into CHOCO to support non-monotonic propagation, the researchers needed to extend all variable classes to include explanations. In addition, the behavior of all constraints in CHOCO needed to be specialized in order to add explanation computation code and to add a method that provides an explanation for every domain modification that the constraint performs.